package com.minminaya.source;

public class Algorithm_15 {

    public static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
    }

    public static boolean hasSubtree(BinaryTreeNode root1, BinaryTreeNode root2) {

        if (root1 == root2) {
            return true;
        }

        if (root2 == null)
            return true;

        if (root1 == null) {
            return false;
        }

        boolean result = false;

        if (root1.value == root2.value) {
            result = match(root1, root2);
        }

        if (result) {
            return true;
        }
        return hasSubtree(root1.left, root2) || hasSubtree(root2.right, root2);
    }

    private static boolean match(BinaryTreeNode root1, BinaryTreeNode root2) {

        if (root1 == root2) {
            return true;
        }

        if (root2 == null) {
            return true;
        }

        if (root1.value == root2.value) {
            return match(root1.left, root2.left) && match(root1.right, root2.right);
        }

        return false;
    }

}
